//给你一棵根节点为 0 的 二叉树 ，它总共有 n 个节点，节点编号为 0 到 n - 1 。同时给你一个下标从 0 开始的整数数组 parents 表示这棵
//树，其中 parents[i] 是节点 i 的父节点。由于节点 0 是根，所以 parents[0] == -1 。 
//
// 一个子树的 大小 为这个子树内节点的数目。每个节点都有一个与之关联的 分数 。求出某个节点分数的方法是，将这个节点和与它相连的边全部 删除 ，剩余部分是若
//干个 非空 子树，这个节点的 分数 为所有这些子树 大小的乘积 。 
//
// 请你返回有 最高得分 节点的 数目 。 
//
// 
//
// 示例 1: 
//
// 
//
// 输入：parents = [-1,2,0,2,0]
//输出：3
//解释：
//- 节点 0 的分数为：3 * 1 = 3
//- 节点 1 的分数为：4 = 4
//- 节点 2 的分数为：1 * 1 * 2 = 2
//- 节点 3 的分数为：4 = 4
//- 节点 4 的分数为：4 = 4
//最高得分为 4 ，有三个节点得分为 4 （分别是节点 1，3 和 4 ）。
// 
//
// 示例 2： 
//
// 
//
// 输入：parents = [-1,2,0]
//输出：2
//解释：
//- 节点 0 的分数为：2 = 2
//- 节点 1 的分数为：2 = 2
//- 节点 2 的分数为：1 * 1 = 1
//最高分数为 2 ，有两个节点分数为 2 （分别为节点 0 和 1 ）。
// 
//
// 
//
// 提示： 
//
// 
// n == parents.length 
// 2 <= n <= 105 
// parents[0] == -1 
// 对于 i != 0 ，有 0 <= parents[i] <= n - 1 
// parents 表示一棵二叉树。 
// 
// Related Topics 树 深度优先搜索 数组 二叉树 
// 👍 91 👎 0

package com.cute.leetcode.editor.cn;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class CountNodesWithTheHighestScore {
    public static void main(String[] args) {
        new CountNodesWithTheHighestScore().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {

        /*public int countHighestScoreNodes1(int[] parents) {
            // 使用Map保存父子关系
            // 采取记忆化递归呢
            // 有两个测试用例没通过，分数计算全用long
            int n = parents.length;
            Map<Integer, int[]> map = new HashMap<>();// 保存父子关系
            for (int i = 1; i < n ; i++) {
                int[] son = map.getOrDefault(parents[i], new int[2]);
                if (son[0] == 0){
                    son[0] = i;
                }else son[1] = i;
                map.put(parents[i], son);
            }
            Map<Integer, Integer> depth = new HashMap<>();//保存子树节点数
            long max = 0L;
            int res = 0;
            for (int i = 0; i < n; i++){
                int temp;
                if (map.containsKey(i)) {// 局部根节点
                    int[] sons = map.get(i);
                    int left  = depth.containsKey(sons[0]) ? depth.get(sons[0]) : dfs(sons[0], map, depth);

                    int right;
                    if (sons[1] == 0) right = 1;
                    else right = depth.containsKey(sons[1]) ? depth.get(sons[1]) : dfs(sons[1], map, depth);

                    if (i == 0) temp = left * right;// 当前节点为根节点
                    else {
                        if (sons[1] != 0) temp = left * right * (n - left - right - 1);
                        else temp = left  * (n - left - 1);
                    }
                }else temp = n - 1;// 叶子节点

                if (temp > max) {
                    max = temp;
                    res = 1;
                }else if (max == temp) res++;
            }
            return res;
        }
        public int dfs(int root, Map<Integer, int[]> map, Map<Integer, Integer> depth){
            // 求当前节点为根节点的节点数
            if (!map.containsKey(root)) return 1;// 叶子节点
            int[] son = map.get(root);// 当前节点为非叶子节点，找子节点
            int left = depth.containsKey(son[0]) ? depth.get(son[0]) : dfs(son[0], map, depth);
            int right;
            if (son[1] == 0) right = 0;
            else right = depth.containsKey(son[1]) ? depth.get(son[1]) : dfs(son[1], map, depth);
            depth.put(root, left + right + 1);// 保存当前为根的节点数
            return left + right + 1;
        }*/

        /**
         * 题解的一个方法，只是保存左右子节点的下标，不真实建立树结构
         */
        private long max = 0;
        private int res = 0;
        public int countHighestScoreNodes(int[] parents) {
            int n = parents.length;
            int[] left = new int[n];// 左子节点
            int[] right = new int[n];// 右子节点
            Arrays.fill(left, -1);
            Arrays.fill(right, -1);
            for (int i = 1; i < n; i++) {
                if (left[parents[i]] == -1) left[parents[i]] = i;
                else right[parents[i]] = i;
            }
            dfs(0, left, right, n);
            return res;
        }


        public int dfs(int node, int[] left, int[] right, int n){
            if (node == -1) return 0;
            int leftNodes = dfs(left[node], left, right, n);// 左子树节点数
            int rightNodes = dfs(right[node], left, right, n);// 右子树节点数
            int remain = n - leftNodes - rightNodes - 1;// 剩余节点数
            long score = help(leftNodes) * help(rightNodes) * help(remain);// 计算分数时必须全用long
            if (score > max) {
                max = score;
                res = 1;
            }else if (score == max) res++;
            return leftNodes + rightNodes + 1;
        }
        public long help(int val){
            return val == 0 ? 1 : val;
        }








    }
//leetcode submit region end(Prohibit modification and deletion)

}